// 设有 N 堆石子石子排成一排，编号为 1, 2, 3 ... N，每堆石子有一定的质量 mi，现在要将这 
// N 堆石子合并成为一堆。每次只能合并相邻的两堆，合并的代价为这两堆石子的质量之和，合并后
// 与这两堆石子相邻的石子将和新堆相邻。合并时由于选择的顺序不同，合并的总代价也不相同。试
// 找出一种合理的方法，使总的代价最小，并输出最小代价。
// 测试链接：https://www.luogu.com.cn/problem/P1775
// 提交以下的code，可以直接通过

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 301;
int n, arr[MAXN], sum[MAXN];
// dp[i][j] 表示把从 i 到 j 合并成一堆的最小代价
int dp[MAXN][MAXN]; 

int read()
{
    char ch = getchar();
    int x = 0, f = 1;
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        x = 10 * x + ch - '0';
        ch = getchar();
    }
    return f * x;
}

int main()
{
    n = read();
    memset(dp, 0x3f, sizeof dp);
    for (int i = 1; i <= n; ++i)
    {
        arr[i] = read();
        sum[i] = sum[i - 1] + arr[i]; // 前缀和
        dp[i][i] = 0;
    }

    for (int len = 2; len <= n; ++len) // 区间长度
    {
        for (int i = 1; i + len - 1 <= n; i++) // 区间左端点
        {
            int j = i + len - 1; // 区间右端点
            for (int k = i; k < j; k++) // 区间分割点
            {
                // sum[j] - sum[i - 1] = sum(a[i ... j])
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + sum[j] - sum[i - 1]);
            }
        }
    }
    printf("%d\n", dp[1][n]);

    return 0;
}